package baseTest;

import java.util.HashMap;

class LRUNode{
    public int value;
    public LRUNode last;
    public LRUNode next;

    public LRUNode(int value) {
        this.value = value;
    }
}
class NodeDoubleLinkedList{
    private LRUNode head;
    private LRUNode tail;

    public NodeDoubleLinkedList(LRUNode head, LRUNode tail) {
        this.head = head;
        this.tail = tail;
    }

    public NodeDoubleLinkedList() {

    }

    public void addNode(LRUNode newNode){
        if (newNode == null){
            return;
        }

        if (this.head == null){
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            newNode.last = this.tail;
            this.tail = newNode;
        }
    }

    public void moveNodeToTail(LRUNode node){
       if (this.tail == node){
           return;
       }

       if (this.head == node){
           this.head = node.next;
           this.head.last = null;
       } else {
           node.last.next = node.next;
           node.next.last = node.last;
       }

       node.last = this.tail;
       node.next = null;
       this.tail.next = node;
       this.tail = node;
    }

    public LRUNode removeHead(){
        if (this.head == null){
            return null;
        }
        LRUNode res = this.head;
        if (this.head == this.tail){
            this.head = null;
            this.tail = null;
        } else {
            this.head = res.next;
            res.next = null;
            this.head.last = null;
        }
        return res;
    }
}
public class LRUCache{
    private HashMap<Integer,LRUNode> keyNodeMap;
    private HashMap<LRUNode,Integer> nodeKeyMap;
    private NodeDoubleLinkedList nodeList;
    private int capacity;

    public LRUCache(int capacity) {
        if (capacity < 1){
            throw new RuntimeException("should be more than 0");
        }
        this.keyNodeMap = new HashMap<Integer,LRUNode>();
        this.nodeKeyMap = new HashMap<LRUNode, Integer>();
        this.nodeList = new NodeDoubleLinkedList();
        this.capacity = capacity;
    }

    public int get(int key){
        if (this.keyNodeMap.containsKey(key)){
            LRUNode res = this.keyNodeMap.get(key);
            this.nodeList.moveNodeToTail(res);
            return res.value;
        }
        return -1;
    }

    public void put(int key, int value){
        if (this.keyNodeMap.containsKey(key)){
            LRUNode node = this.keyNodeMap.get(key);
            node.value = value;
            this.nodeList.moveNodeToTail(node);
        } else {
            LRUNode newNode = new LRUNode(value);
            this.keyNodeMap.put(key,newNode);
            this.nodeKeyMap.put(newNode,key);
            this.nodeList.addNode(newNode);
            if (this.keyNodeMap.size() == this.capacity+1){
                this.removeMostUnusedCache();
            }
        }
    }

    private void removeMostUnusedCache(){
        LRUNode removeNode = this.nodeList.removeHead();
        int removeKey = this.nodeKeyMap.get(removeNode);
        this.nodeKeyMap.remove(removeNode);
        this.keyNodeMap.remove(removeKey);
    }
}
